home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / general / glob.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  14KB  |  538 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Guido van Rossum.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)glob.c    5.12 (Berkeley) 6/24/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  43.  *
  44.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  45.  *
  46.  * Optional extra services, controlled by flags not defined by POSIX:
  47.  *
  48.  * GLOB_QUOTE:
  49.  *    Escaping convention: \ inhibits any special meaning the following
  50.  *    character might have (except \ at end of string is retained).
  51.  * GLOB_MAGCHAR:
  52.  *    Set in gl_flags if pattern contained a globbing character.
  53.  * gl_matchc:
  54.  *    Number of matches in the current invocation of glob.
  55.  */
  56.  
  57. #define KERNEL
  58. #include "ixemul.h"
  59. #include "kprintf.h"
  60.  
  61. #undef DEBUG
  62.  
  63. #include <sys/cdefs.h>
  64. #include <dirent.h>
  65. #include <glob.h>
  66. #include <ctype.h>
  67. #include <string.h>
  68. #include <stdio.h>
  69. #include <stdlib.h>
  70.  
  71. #undef NOT    /* in <intuition/intuition.h> on AmigaDOS */
  72.  
  73. #define    DOLLAR        '$'
  74. #define    DOT        '.'
  75. #define    EOS        '\0'
  76. #define    LBRACKET    '['
  77. #define    NOT        '!'
  78. #define    QUESTION    '?'
  79. #define    QUOTE        '\\'
  80. #define    RANGE        '-'
  81. #define    RBRACKET    ']'
  82. #define    SEP        '/'
  83. #define    STAR        '*'
  84. #define    TILDE        '~'
  85. #define    UNDERSCORE    '_'
  86. #define HASH            '#'
  87.  
  88. #define    M_QUOTE        0x8000
  89. #define    M_PROTECT    0x4000
  90. #define    M_MASK        0xffff
  91. #define    M_ASCII        0x00ff
  92.  
  93. #define    CHAR(c)        ((c)&M_ASCII)
  94. #define    META(c)        ((c)|M_QUOTE)
  95. #define    M_ALL        META('*')
  96. #define    M_END        META(']')
  97. #define    M_NOT        META('!')
  98. #define    M_ONE        META('?')
  99. #define    M_RNG        META('-')
  100. #define    M_SET        META('[')
  101. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  102.  
  103. typedef u_short Char;
  104.  
  105. static int     compare __P((const void *, const void *));
  106. static int     icompare __P((const void *, const void *));
  107. static void     g_Ctoc __P((Char *, char *));
  108. static DIR    *g_opendir __P((Char *));
  109. static Char    *g_strchr __P((Char *, int));
  110. static int     g_stat __P((Char *, struct stat *));
  111. static int     glob1 __P((Char *, glob_t *));
  112. static int     glob2 __P((Char *, Char *, Char *, glob_t *));
  113. static int     glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
  114. static int     globextend __P((Char *, glob_t *));
  115. static int     match __P((Char *, Char *, Char *, int));
  116.  
  117. /*
  118.  * The main glob() routine: compiles the pattern (optionally processing
  119.  * quotes), calls glob1() to do the real pattern matching, and finally
  120.  * sorts the list (unless unsorted operation is requested).  Returns 0
  121.  * if things went well, nonzero if errors occurred.  It is not an error
  122.  * to find no matches.
  123.  */
  124. int glob(const  char *pattern, int flags, int (*errfunc)(char *, int), glob_t *pglob)
  125. {
  126.     const u_char *compilepat, *patnext;
  127.     int c, err, oldpathc;
  128.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  129.     char *glob_pattern = (char *)pattern;
  130.  
  131.         if (index(pattern, ':'))
  132.           {
  133.             char *colon;
  134.  
  135.             glob_pattern = alloca(strlen(pattern) + 2);
  136.             strcpy(glob_pattern + 1, pattern);
  137.             *glob_pattern = '/';
  138.             colon = index(glob_pattern, ':');
  139.             *colon = '/';
  140.           }
  141.     patnext = (u_char *) glob_pattern;
  142.     if (!(flags & GLOB_APPEND)) {
  143.         pglob->gl_pathc = 0;
  144.         pglob->gl_pathv = NULL;
  145.         if (!(flags & GLOB_DOOFFS))
  146.             pglob->gl_offs = 0;
  147.     }
  148.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  149.     pglob->gl_errfunc = errfunc;
  150.     oldpathc = pglob->gl_pathc;
  151.     pglob->gl_matchc = 0;
  152.  
  153.     bufnext = patbuf;
  154.     bufend = bufnext + MAXPATHLEN;
  155.     compilebuf = bufnext;
  156.     compilepat = patnext;
  157.     if (flags & GLOB_QUOTE) {
  158.         /* Protect the quoted characters. */
  159.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  160.             if (c == QUOTE) {
  161.                 if ((c = *patnext++) == EOS) {
  162.                     c = QUOTE;
  163.                     --patnext;
  164.                 }
  165.                 *bufnext++ = c | M_PROTECT;
  166.             }
  167.             else
  168.                 *bufnext++ = c;
  169.     }
  170.     else 
  171.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  172.             *bufnext++ = c;
  173.     *bufnext = EOS;
  174.  
  175.     bufnext = patbuf;
  176.     qpatnext = patbuf;
  177.     /* We don't need to check for buffer overflow any more. */
  178.     while ((c = *qpatnext++) != EOS) {
  179.         switch (c) {
  180.         case LBRACKET:
  181.             pglob->gl_flags |= GLOB_MAGCHAR;
  182.             c = *qpatnext;
  183.             if (c == NOT)
  184.                 ++qpatnext;
  185.             if (*qpatnext == EOS ||
  186.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  187.                 *bufnext++ = LBRACKET;
  188.                 if (c == NOT)
  189.                     --qpatnext;
  190.                 break;
  191.             }
  192.             *bufnext++ = M_SET;
  193.             if (c == NOT)
  194.                 *bufnext++ = M_NOT;
  195.             c = *qpatnext++;
  196.             do {
  197.                 *bufnext++ = CHAR(c);
  198.                 if (*qpatnext == RANGE &&
  199.                     (c = qpatnext[1]) != RBRACKET) {
  200.                     *bufnext++ = M_RNG;
  201.                     *bufnext++ = CHAR(c);
  202.                     qpatnext += 2;
  203.                 }
  204.             } while ((c = *qpatnext++) != RBRACKET);
  205.             *bufnext++ = M_END;
  206.             break;
  207.         case QUESTION:
  208.             pglob->gl_flags |= GLOB_MAGCHAR;
  209.             *bufnext++ = M_ONE;
  210.             break;
  211.         case STAR:
  212.             pglob->gl_flags |= GLOB_MAGCHAR;
  213.             *bufnext++ = M_ALL;
  214.             break;
  215.         case HASH:
  216.             if ((flags & GLOB_AMIGA) && *qpatnext == QUESTION)
  217.             {
  218.               qpatnext++;
  219.               pglob->gl_flags |= GLOB_MAGCHAR;
  220.               *bufnext++ = M_ALL;
  221.               break;
  222.             }
  223.             /* fall through */
  224.         default:
  225.             *bufnext++ = CHAR(c);
  226.             break;
  227.         }
  228.     }
  229.     *bufnext = EOS;
  230. #ifdef DEBUG
  231.     qprintf(patbuf);
  232. #endif
  233.  
  234.     if ((err = glob1(patbuf, pglob)) != 0)
  235.         return(err);
  236.  
  237.     if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
  238.         if (!(flags & GLOB_QUOTE)) {
  239.             Char *dp = compilebuf;
  240.             const u_char *sp = pattern;
  241.             while ((*dp++ = *sp++));
  242.         }
  243.         else {
  244.             /*
  245.              * Copy pattern, interpreting quotes; this is slightly
  246.              * different than the interpretation of quotes above
  247.              * -- which should prevail?
  248.              */
  249.             while (*pattern != EOS) {
  250.                 if (*pattern == QUOTE) {
  251.                     if (*++pattern == EOS)
  252.                         --pattern;
  253.                 }
  254.                 *compilebuf++ = (u_char)*pattern++;
  255.             }
  256.             *compilebuf = EOS;
  257.         }
  258.         return(globextend(patbuf, pglob));
  259.     } else if (!(flags & GLOB_NOSORT)) 
  260.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  261.             pglob->gl_pathc - oldpathc, sizeof(char *),
  262.                     (flags & GLOB_NOCASE) ? icompare : compare);
  263.     return(0);
  264. }
  265.  
  266. static int
  267. compare(p, q)
  268.     const void *p, *q;
  269. {
  270.     return(strcmp(*(char **)p, *(char **)q));
  271. }
  272.  
  273. static int
  274. icompare(p, q)
  275.     const void *p, *q;
  276. {
  277.     return(strcasecmp(*(char **)p, *(char **)q));
  278. }
  279.  
  280. static int glob1(Char *pattern, glob_t *pglob)
  281. {
  282.     Char pathbuf[MAXPATHLEN+1];
  283.  
  284.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  285.     if (*pattern == EOS)
  286.         return(0);
  287.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  288. }
  289.  
  290. /*
  291.  * The functions glob2 and glob3 are mutually recursive; there is one level
  292.  * of recursion for each segment in the pattern that contains one or more
  293.  * meta characters.
  294.  */
  295. static int glob2(Char *pathbuf, Char *pathend, Char *pattern, glob_t *pglob)
  296. {
  297.     struct stat sb;
  298.     Char *p, *q;
  299.     int anymeta;
  300.  
  301.     /*
  302.      * Loop over pattern segments until end of pattern or until
  303.      * segment with meta character found.
  304.      */
  305.     for (anymeta = 0;;) {
  306.         if (*pattern == EOS) {        /* End of pattern? */
  307.             *pathend = EOS;
  308.             if (g_stat(pathbuf, &sb))
  309.                 return(0);
  310.         
  311.             if (((pglob->gl_flags & GLOB_MARK) &&
  312.                 pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
  313.                 || (S_ISLNK(sb.st_mode) &&
  314.                 (g_stat(pathbuf, &sb) == 0) &&
  315.                 S_ISDIR(sb.st_mode)))) {
  316.                 *pathend++ = SEP;
  317.                 *pathend = EOS;
  318.             }
  319.             ++pglob->gl_matchc;
  320.             return(globextend(pathbuf, pglob));
  321.         }
  322.  
  323.         /* Find end of next segment, copy tentatively to pathend. */
  324.         q = pathend;
  325.         p = pattern;
  326.         while (*p != EOS && *p != SEP) {
  327.             if (ismeta(*p))
  328.                 anymeta = 1;
  329.             *q++ = *p++;
  330.         }
  331.  
  332.         if (!anymeta) {        /* No expansion, do next segment. */
  333.             pathend = q;
  334.             pattern = p;
  335.             while (*pattern == SEP)
  336.                 *pathend++ = *pattern++;
  337.         } else            /* Need expansion, recurse. */
  338.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  339.     }
  340.     /* NOTREACHED */
  341. }
  342.  
  343. static int glob3(Char *pathbuf, Char *pathend, Char *pattern, Char *restpattern, glob_t *pglob)
  344. {
  345.     register struct dirent *dp;
  346.     DIR *dirp;
  347.     int err;
  348.  
  349.     *pathend = EOS;
  350.     errno = 0;
  351.     KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  352.         
  353.     if (!(dirp = g_opendir(pathbuf)))
  354.         /* TODO: don't call for ENOENT or ENOTDIR? */
  355.         if ((pglob->gl_errfunc && (*pglob->gl_errfunc)(pathbuf, errno)) ||
  356.             (pglob->gl_flags & GLOB_ERR))
  357.             return(GLOB_ABEND);
  358.         else
  359.             return(0);
  360.  
  361.     err = 0;
  362.  
  363.     /* Search directory for matching names. */
  364.     while ((dp = (struct dirent *)syscall(SYS_readdir, dirp))) {
  365.         register u_char *sc;
  366.         register Char *dc;
  367.  
  368.         /* Initial DOT must be matched literally. */
  369.         if (dp->d_name[0] == DOT && *pattern != DOT)
  370.             continue;
  371.         for (sc = (u_char *) dp->d_name, dc = pathend; (*dc++ = *sc++); ) ;
  372.         if (!match(pathend, pattern, restpattern, pglob->gl_flags & GLOB_NOCASE)) {
  373.             *pathend = EOS;
  374.             continue;
  375.         }
  376.         err = glob2(pathbuf, --dc, restpattern, pglob);
  377.         if (err)
  378.             break;
  379.     }
  380.  
  381.     /* TODO: check error from readdir? */
  382.     syscall(SYS_closedir, dirp);
  383.     return(err);
  384. }
  385.  
  386.  
  387. /*
  388.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  389.  * add the new item, and update gl_pathc.
  390.  *
  391.  * This assumes the BSD realloc, which only copies the block when its size
  392.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  393.  * behavior.
  394.  *
  395.  * Return 0 if new item added, error code if memory couldn't be allocated.
  396.  *
  397.  * Invariant of the glob_t structure:
  398.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  399.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  400.  */
  401. static int globextend(Char *path, glob_t *pglob)
  402. {
  403.     register char **pathv;
  404.     register int i;
  405.     u_int newsize;
  406.     char *copy;
  407.     Char *p;
  408.  
  409.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  410.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  411.     if (pathv == NULL)
  412.         return(GLOB_NOSPACE);
  413.  
  414.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  415.         /* first time around -- clear initial gl_offs items */
  416.         pathv += pglob->gl_offs;
  417.         for (i = pglob->gl_offs; --i >= 0; )
  418.             *--pathv = NULL;
  419.     }
  420.     pglob->gl_pathv = pathv;
  421.  
  422.     for (p = path; *p++;);
  423.     if ((copy = malloc(p - path)) != NULL) {
  424.         g_Ctoc(path, copy);
  425.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  426.     }
  427.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  428.     return(copy == NULL ? GLOB_NOSPACE : 0);
  429. }
  430.  
  431.  
  432. /*
  433.  * pattern matching function for filenames.  Each occurrence of the *
  434.  * pattern causes a recursion level.
  435.  */
  436. static int match(Char *name, Char *pat, Char *patend, int nocase)
  437. {
  438.     int ok, negate_range;
  439.     Char c, k;
  440.  
  441.     while (pat < patend) {
  442.         c = *pat++;
  443.         switch (c & M_MASK) {
  444.         case M_ALL:
  445.             if (pat == patend)
  446.                 return(1);
  447.             for (; *name != EOS; ++name)
  448.                 if (match(name, pat, patend, nocase))
  449.                     return(1);
  450.             return(0);
  451.         case M_ONE:
  452.             if (*name++ == EOS)
  453.                 return(0);
  454.             break;
  455.         case M_SET:
  456.             ok = 0;
  457.             k = *name++;
  458.             if (nocase)
  459.               k = tolower(k);
  460.             if ((negate_range = ((*pat & M_MASK) == M_NOT)))
  461.                 ++pat;
  462.             while (((c = *pat++) & M_MASK) != M_END) {
  463.                     if (nocase)
  464.                             c = tolower(c);
  465.                 if ((*pat & M_MASK) == M_RNG) {
  466.                     if (c <= k && k <= (nocase ? tolower(pat[1]) : pat[1]))
  467.                         ok = 1;
  468.                     pat += 2;
  469.                 } else if (c == k)
  470.                     ok = 1;
  471.                         }
  472.             if (ok == negate_range)
  473.                 return(0);
  474.             break;
  475.         default:
  476.                 if (nocase)
  477.                 {
  478.                   k = *name++;
  479.                   if (tolower(k) != tolower(c))
  480.                     return 0;
  481.                 }
  482.             else if (*name++ != c)
  483.                 return(0);
  484.             break;
  485.         }
  486.     }
  487.     return(*name == EOS);
  488. }
  489.  
  490. /* Free allocated data belonging to a glob_t structure. */
  491. void globfree(glob_t *pglob)
  492. {
  493.     register int i;
  494.     register char **pp;
  495.  
  496.     if (pglob->gl_pathv != NULL) {
  497.         pp = pglob->gl_pathv + pglob->gl_offs;
  498.         for (i = pglob->gl_pathc; i--; ++pp)
  499.             if (*pp)
  500.                 free(*pp);
  501.         free(pglob->gl_pathv);
  502.     }
  503. }
  504.  
  505. static DIR *g_opendir(Char *str)
  506. {
  507.     char buf[MAXPATHLEN];
  508.  
  509.     if (!*str)
  510.         return (DIR *)syscall(SYS_opendir, ".");
  511.     g_Ctoc(str, buf);
  512.     return (DIR *)syscall(SYS_opendir, buf);
  513. }
  514.  
  515. static int g_stat(Char *fn, struct stat *sb)
  516. {
  517.     char buf[MAXPATHLEN];
  518.  
  519.     g_Ctoc(fn, buf);
  520.     return syscall(SYS_stat, buf, sb);
  521. }
  522.  
  523. static Char *g_strchr(Char *str, int ch)
  524. {
  525.     do {
  526.         if (*str == ch)
  527.             return (str);
  528.     } while (*str++);
  529.     return (NULL);
  530. }
  531.  
  532. static void g_Ctoc(Char *str, char *buf)
  533. {
  534.     register char *dc;
  535.  
  536.     for (dc = buf; (*dc++ = *str++); ) ;
  537. }
  538.